The present invention relates to optimization methods and more particularly, to a system and method for optimizing allocation of multi-service traffic concentrators in a telecommunications network by employing linear programming.
A typical telecommunications network includes, transmission components, switching components and facilities for maintaining equipment. Transmission components or links are the media used to transmit signals. Switching components or nodes include transmitters and receivers for voice and data and routers for routing using circuit-switching techniques. The transmission components in the local loop are largely made of copper twisted-pair wiring with the long distance service providers, i.e., the interexchange carriers providing services between local carriers, generally employ fiber-optic cables and radio systems for their backbone trunks and long distance lines. In such a communication network, it is highly desirable to allocate the transmission and switching components optimally such that every component in the network is utilized to its maximum capacity. Furthermore, in order to automate such an optimization procedure, it is also highly desirable to implement a solution that employs a mathematical technique such as linear programming.
Linear programming is generally concerned with the maximization or minimization of a linear object function having many variable terms subject to linear equality and inequality constraints. In its application, linear programming provides the ability to state general objectives or goals and to find optimal policy solutions, i.e., to determine detailed decisions to be taken in order to xe2x80x9cbestxe2x80x9d achieve these goals when faced with practical situations or decision problems of great complexity. An example of an objective may be to minimize total costs or maximize profits measured in monetary units. In other applications, the objective may be to minimize direct labor costs or to maximize the number of assembled parts.
In its implementation, linear programming encompasses models that formulate real word problems in detailed mathematical terms, the algorithm that solve the models and the software that executes the algorithm on computers based on the mathematical theory. Commercial software is presently available for solving linear problems implemented with known mathematical theory, such as the universally known Simplex Method. However, before the software may be used to compute a solution using various mathematical algorithm, a mathematical model representing the real world problem must be built and programmed as an input to the existing software.
Building the mathematical model which represents a specific objective desired in a specific situation or practical application in the real world is frequently referred to as the model formulation or the problem formulation. Although general algorithm for solving linear problems are well known, the formulation of the linear problem is unique to each situation involving various decision making processes and requires an exact artistry to procure the most efficient solution possible. Models of the real world are not always easy to formulate because of the diversity and ambiguity that exists in the real world or because of the ambiguous understanding of it. For instance, linear problem models can be very large in practice, some having many thousands of constraints and variables. Yet, it is possible to abstract a real world problem and formulate it as a collection of mathematical relationships which characterize the set of feasible solutions to that problem. Consequently, it is well known in the field of mathematics that the process of the initial problem formulation is considered an essential and important aspect equally as solving it and merits a field of technological art in itself. Thus, in linear problem programming, it is highly desirable to define and formulate a linear problem well and suited to each unique situation, such that the most optimal solution may be obtained.
Formulating linear problems involves defining decision variables which represent the quantity to be controlled for optimal efficiency, defining item sets or data sets, and setting up constraints and objective functions. Item sets represent the classes or objects that are required as inputs or outputs in a system. Constraints refer to set of rules to which the solution must conform, and the objective function defines the goal desired in a practical application expressed in terms of a mathematical equation. Although there is more than one way to formulate a known problem, only a correct formulation will result in a correct solution. Moreover, the number of decision variables and constraints defined dictates whether or not a correct solution by linear programming can be attained quickly and efficiently. For example, depending on how well the problem is formulated and defined, a linear problem program can take from hours to days to execute before determining a solution. Thus, in linear programming it is also highly desirable to formulate a given problem in a most efficient manner such that a solution may be obtained quickly and efficiently.
In a typical network layout or design, it is always highly desirable to be able to minimize the cost of networking by allocating network circuit equipment including the communication servers, nodes, devices, lines and trunks in a most optimal manner, thereby balancing the available resources such that any unused surplus is utilized and a shortage of resources is avoided. Advantageously, and as described above with reference to linear programming, such network optimization problem provides an ideal application for solution by linear programming. Therefore, it is highly desirable to find an optimal allocation of communication components in a telecommunications network topology employing a linear programming method.
The present invention provides a system and method for optimally allocating multi-service traffic concentrators in telecommunications network by formulating a unique problem model in terms of mathematical expressions which represents the telecommunications network topology such that the model may be input to a linear programming algorithm for obtaining the most optimal allocation or layout of the network components. To conform to the rules of the linear programming, data set indices, decision variables, constraints and objective functions are selected and defined as parameters that represent the telecommunications network topology.
Data set indices are defined as those components and/or factors in the telecommunications network which affect various operations of the network, and include origination, concentration and destination sites as well as different multiplexer levels at each of the sites. Decision variables representing measures of efficiency in the network and whose optimal values are to be computed by the linear program are defined to include concentrator node selection, concentrator to destination site connection status, and the number of optical carrier trunks for each concentrator. The values for each of the three variables represent the equipment quantity for optimally allocating multi-service traffic concentrators.
The objective function to be minimized is defined as the sum of: the total transmission cost between selected origination sites and selected concentration sites; the total transmission cost between selected concentration sites and selected destination sites; the total unit cost of concentrators; the total port cost on the low side of the concentrators; and the total optical carrier level port cost on the high side of the concentrators and the destination switches. Thus, in setting up the objective function, the transmission costs, the unit costs of equipment, and the backbone switch ports are considered.
Further, the minimization of the objective function is computed subject to the unique constraints defined in the present invention. These constraints include conditions that one concentration site be assigned for any one origination site, that an origination site is enabled to be connected to a concentration site, and that there be a balance between the low and high side of the concentrators, i.e., the total capacity on low side must not exceed the capacity available on the high side of the concentrator. The latter constraint prevents any occurrence of a potential bottleneck at the concentrators.
In addition, a baseline network parameter which represents the cost of non-optimized network is determined by summing the transmission cost between origination and destination sites with the backbone switch port cost. This baseline network parameter is used as a baseline comparison to the optimized network cost.
The present invention provides the concentrator equipment facilities and their allocation arrangement in the network as the measure of that network""s efficiency. Consequently, in the present invention, the concentrator related equipment is computed as decision variables in linear programming which would provide an optimal network topology with optimal number of traffic concentrators present.
Moreover, the present invention utilizes a relatively small number of variables and constraints such that the optimal values are computed quickly and efficiently by the linear program. Such quick and efficient calculations of linear programming provides a reduction in the cost of running the program, enabling modulation of the various parameters, variables and even the constraints, in search of the most optimally possible network with given traffic usage. Further yet, with the model built and automated, the model may easily be modified by changing one or more input variables for updating as well as for adapting the model to another similar network design.
Further features and advantages of the present invention as well as the structure and operation of various embodiments of the present invention are described in detail below with reference to the accompanying drawings. In the drawings, like reference numbers indicate identical or functionally similar elements.